#include <stdio.h>
#include <stdlib.h>

/**
 * 顺序表(数组)实现队列，队尾插入，队头取出
 *
 * 顺序表在实现时就是用数组来实现
 * 顺序表实现队列，就是用数组来实现
 *
 * 队列中添加数据是无限的，数组是有长度的，似乎是冲突的
 *
 * 队列都会有入队与出队，入队就是在数组中写入数据，出队是删除数组中的数据
 * 出队后删除数据的位置可以继续存放新的数据，因此如果数组能形成一个环，则满足队列的要求
 *
 * 通过控制数组的索引可以形成一个闭环
 * 
 * 设数组总长度为size，队头索引为 head，队尾索引为 tail
 * 
 * 入队时，索引为  (tail + 1) % size
 * 出队时，索引为  head
 * 队空时， head == tail
 * 队满时， (tail + 1) == head
 *
 * 实现的功能如下：
 * 1. 创建链表
 * 2. 入队
 * 3. 出队
 * 4. 取出队头元素
 * 5. 判断队列是否为空
 * 6. 判断队列是否已满
 * 7. 清空队列
 * 8. 销毁队列
 * 9. 打印队列
 */

typedef int data_t;
typedef struct queue {
    int head;                 //队头索引
    int tail;                 //队尾索引
    int size;                 //队列尺寸，
    int total;                //队列尺寸，
    data_t data[0];
} queue_t;

queue_t *create_queue(int size) {
    queue_t *q;
    q = malloc(sizeof(queue_t) + size * sizeof(data_t));
    q->size = size;
    q->head = 0;
    q->tail = 0;
    q->total = 0;
    return q;
}

int in_queue(queue_t *q, data_t *d) {
    int next;
    next = (q->tail + 1) % q->size;

    //队已满
    if(next == q->head) return -1;
    
    q->data[next] = *d;
    q->tail = (q->tail + 1) % q->size;
    q->total++;

    return 0;
}

int out_queue(queue_t *q, data_t *response) {
    int index;
    if(q->head == q->tail) return -1;
    index = (q->head + 1) % q->size;
    *response = q->data[index];
    q->head = index;
    q->total--;

    return 0;
}

int get_head_queue(queue_t *q, data_t *response) {
    *response = q->data[q->head];
    return 0;
}

int is_empty_queue(queue_t *q) {
    return q->head == q->tail ? 1 : 0;
}

//清空队列，意味着头元素还存在，将tail指向头
int clean_queue(queue_t *q) {
    q->head = 0;
    q->tail = 0;
    q->total = 0;
    return 0;
}

int destory_queue(queue_t **qq) {
    free(*qq);
    *qq = NULL;

    return 0;
}

void print_queue(queue_t *q) {
    int head;
    if(is_empty_queue(q)) {
        printf("当前队列(共：%d)无数据", q->total);
    } else {
        printf("当前队列(共：%d)为：", q->total);
        int i, index;
        for(i = 0; i < q->total; i++) {
            index = (q->head + i + 1) % q->size; 
            printf("%d ", q->data[index]);
        }
    }
    printf("\n");
}

int main(int argc, const char *argv[]) 
{
    queue_t *q;
    data_t *response;
    q = create_queue(20);
    int i;
    for(i = 0; i < 10; i++) {
        in_queue(q, &i);
    }
    print_queue(q);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    out_queue(q, response);
    printf("出队：%d\n", *response);

    print_queue(q);

    get_head_queue(q, response);
    printf("获取队顶元素：%d\n", *response);

    clean_queue(q);
    printf("清空队列后，判断队列是否为空：%d\n", is_empty_queue(q));
    print_queue(q);

    printf("重新加入数据：\n");
    for(i = 100; i < 110; i++) {
        in_queue(q, &i);
    }
    print_queue(q);

    /*
    //此处有bug
    destory_queue(&q);
    if(NULL == q) {
        printf("队列已销毁成功\n");
    } else {
        printf("队列已销毁失败\n");
    }
    */

}


